#include "util.h"
#include "common_sort.h"

/*
冒泡排序时间复杂度
在外层循环每次减少时，内层循环次数从0到i-1

T(n) = (n-1)+(n-2)+(n-3)+...+0  // 此为等差数列
     = n*(n+1)/ 2
	 = O(n^2)

*/

void BubbleSort::sort(std::vector<int>& vec) {
	int len = vec.size();

	bool flag = true;
	for (int i = len - 1; i >= 0 && flag; --i) {
		flag = false;
		for (int j = 0; j < i; ++j) {
			if (vec[j] > vec[j + 1]) {
				util::swap(vec, j, j + 1);
				flag = true;
			}
		}
	}
}

